/**
 * Problem from "Introduction to Algorithms" Cormen, Charles, Leiserson, Rivest, Stein
 * Task C.2-3
 * Suppose we shuffle a deck of 10 cards, each bearing a distinct number from 1 to 10,
 * to mix the cards thoroughly. We then remove three cards, one at a time, from deck. What is the
 * probability that we select the three cards in sorted(increasing) order?
 *
 * Program generates shuffle cards deck with using sorting array with priorities, then conducting experiments.
 * After that compute probability. Probability must be approximatly equal to 1.0 / 6.0
 *
 * See also insertation sort(2.1), randomly permuting array(5.3)
 *
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

const int deckSize = 10;
const int experiments = 10000000;

int *createDeck(int deckSize) {
    int *deck = malloc(sizeof(int)*deckSize);

    for(int i=0; i<deckSize; i++) {
        deck[i] = i;
    }

    return deck;
}

void shuffleDeck(int *deck, int deckSize) {
    int priorities[deckSize];

    for(int i=0; i<deckSize; i++) {
        priorities[i] = random();
    }

    for(int i=1; i<deckSize; i++) {
        int j = i - 1;
        int v = priorities[i];
        int deckV = deck[i];
        while((priorities[j] > v) && (j > -1)) {
            j--;
        }

        do {
            int tmp = priorities[j + 1];
            int deckTmp = deck[j+1];
            priorities[j + 1] = v;
            deck[j + 1] = deckV;

            v = tmp;
            deckV = deckTmp;
            j++;
        } while(j < i);
    }
}

int hasEquals(int *cards, int cardsCount) {
    for(int i=0; i<cardsCount; i++) {
        for(int j=(i+1); j<cardsCount; j++) {
            if(cards[i] == cards[j]) {
                return 1;
            }
        }
    }
    return 0;
}

int *chooseCards(int *deck, int deckSize, int cardsCount) {
    int *cards = malloc(sizeof(int)*deckSize);

    do {
        for(int i = 0; i < cardsCount; i++) {
            cards[i] = deck[random() % deckSize];
        }
    } while(hasEquals(cards, cardsCount));

    return cards;
}

int main()
{
    int successFull = 0;

    srand(time(NULL));

    int *deck = createDeck(deckSize);
    shuffleDeck(deck, deckSize);

    for(int i = 0; i<experiments; i++) {
        int* cards = chooseCards(deck, deckSize, 3);

        if((cards[0] < cards[1]) && (cards[1] < cards[2])) {
            successFull++;
        }

        free(cards);
    }

    double p = (((double)successFull) / experiments);
    printf("Probability %f = 1/%f\n", p, 1.0 / p);
    printf("Calculated %f\n", 1.0 / 6.0);

    free(deck);
    return 0;
}
